home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 038a / in_sort.zip / QUICKSRT.QB < prev   
Text File  |  1991-05-01  |  2KB  |  64 lines
  1. 10  REM     Written 8/28/85;  by James Haley
  2. 20  REM     non-recursive quicksort in basic
  3. 30  REM
  4. 40  OPTION BASE 1          ' all arrays start with 1, not zero
  5. 50  DEFINT A-Z             ' make all variables integers
  6. 60  DIM VECTOR(10000)        ' the array to be sorted
  7. 70  DIM STACK.LEFT(32)     ' keeps track of what to sort
  8. 80  DIM STACK.RIGHT(32)    ' keeps track of what to sort
  9. 90  REM
  10. 100  REM    read in an array to sort
  11. 110  REM    SORT.NUM contains the number of things to sort
  12. 120  REM
  13. 130  SORT.NUM = 0
  14. 140 INPUT "how many elements do you want to sort ";COUNT
  15. 150 FOR K = 1 TO COUNT
  16. 160    SORT.NUM = SORT.NUM + 1
  17. 170    VECTOR(SORT.NUM) = INT(RND*1000)
  18. 180 NEXT K
  19. 190 PRINT TIME$
  20. 200 REM
  21. 210 REM initialize the stack
  22. 220 REM
  23. 230 STACK.POINTER = 1
  24. 240 STACK.LEFT(STACK.POINTER) = 1         ' this is the first thing to sort
  25. 250 STACK.RIGHT(STACK.POINTER) = SORT.NUM ' this is the last thing to sort
  26. 260 REM
  27. 270 REM get the right and left limits of the array to sort from the stack
  28. 280 REM top of sort loop
  29. 290 REM
  30. 300   LEFT = STACK.LEFT(STACK.POINTER)
  31. 310   RIGHT = STACK.RIGHT(STACK.POINTER)
  32. 320   STACK.POINTER = STACK.POINTER - 1
  33. 330   REM
  34. 340   REM decide if this partition is sorted
  35. 350   REM
  36. 360   IF LEFT >= RIGHT THEN IF STACK.POINTER > 0 THEN GOTO 300 ELSE GOTO 570
  37. 370   REM
  38. 380   REM partition the array around the pivot
  39. 390   REM
  40. 400   I = LEFT
  41. 410   J = RIGHT + 1
  42. 420   PIVOT = VECTOR( LEFT )
  43. 430      J = J - 1 : IF VECTOR(J) > PIVOT GOTO 430
  44. 440      I = I + 1 : IF (VECTOR(I) < PIVOT) AND (I < RIGHT) GOTO 440
  45. 450      IF I < J THEN SWAP VECTOR(I), VECTOR(J)  : GOTO 430
  46. 460   SWAP  VECTOR(LEFT), VECTOR(J)
  47. 470   REM
  48. 480   REM set up stack for the sub-partitions
  49. 490   REM
  50. 500   STACK.POINTER = STACK.POINTER + 1     ' increment the stack
  51. 510   STACK.LEFT(STACK.POINTER) = J + 1     ' for the right side
  52. 520   STACK.RIGHT(STACK.POINTER) = RIGHT    ' partition
  53. 530   STACK.POINTER = STACK.POINTER + 1     ' increment the stack
  54. 540   STACK.LEFT(STACK.POINTER) = LEFT      ' for the left side
  55. 550   STACK.RIGHT(STACK.POINTER) = J - 1    ' partition
  56. 560   GOTO 300     ' go back and sort the next sub-partition
  57. 570 PRINT TIME$
  58. 580 REM
  59. 590 REM sort finished, print out the sorted array
  60. 600 REM
  61. 610 FOR K = 1 TO SORT.NUM
  62. 620   PRINT VECTOR(K);
  63. 630 NEXT K : PRINT
  64.